{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count All Valid Pickup and Delivery Options"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming #combinatorics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划 #组合数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countOrders"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有效的快递序列数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你&nbsp;<code>n</code>&nbsp;笔订单，每笔订单都需要快递服务。</p>\n",
    "\n",
    "<p>计算所有有效的 取货 / 交付 可能的顺序，使 delivery(i) 总是在 pickup(i) 之后。</p>\n",
    "\n",
    "<p>由于答案可能很大，请返回答案对 10^9 + 7 取余的结果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>只有一种序列 (P1, D1)，物品 1 的配送服务（D1）在物品 1 的收件服务（P1）后。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>所有可能的序列包括：\n",
    "(P1,P2,D1,D2)，(P1,P2,D2,D1)，(P1,D1,P2,D2)，(P2,P1,D1,D2)，(P2,P1,D2,D1) 和 (P2,D2,P1,D1)。\n",
    "(P1,D2,P2,D1) 是一个无效的序列，因为物品 2 的收件服务（P2）不应在物品 2 的配送服务（D2）之后。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3\n",
    "<strong>输出：</strong>90\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 500</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-all-valid-pickup-and-delivery-options](https://leetcode.cn/problems/count-all-valid-pickup-and-delivery-options/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-all-valid-pickup-and-delivery-options](https://leetcode.cn/problems/count-all-valid-pickup-and-delivery-options/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1', '2', '3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        return ((n*2 - 1) * n * self.countOrders(n-1)) % (10**9+7)  # use * since n and n-1 are independent!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        mod=10**9+7\n",
    "        if n==1:return 1\n",
    "        f=[0]*(n*2+10)\n",
    "        f[0]=1\n",
    "        for i in range(1,n+1):\n",
    "            x=(n-i+1)\n",
    "            f[i]=x*(2*x-1)*f[i-1]%mod\n",
    "        return  f[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        res, mod = 1, int(1e9+7)\n",
    "        for i in range(2, n+1):\n",
    "            res = res * (i*2-1)*i % mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        ans, mod = 1, int(1e9 + 7)\n",
    "        for i in range(2, n + 1):\n",
    "            ans = ans * (i * 2 - 1) * i % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        mod=10**9+7\n",
    "        ans=1\n",
    "        for i in range(2,n+1):\n",
    "            ans=ans*(i*2-1)*i%mod\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "dp = [0]*501\n",
    "dp[1] = 1\n",
    "for i in range(2, 501):\n",
    "    dp[i] = dp[i-1]*(2*i-1)*i\n",
    "    dp[i] %= MOD\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        # 1 2 3 4\n",
    "        # C(2 * n + 1, 1) + C(2 * n + 1, 2) \n",
    "        # 2 * n + 1 + (2 * n + 1) * (2 * n) // 2\n",
    "        # 2 * n + 1 + (2 * n + 1) * (n)\n",
    "        # (2 * n + 1) * (n + 1)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        ans = 1\n",
    "        for i in range(2, n + 1):\n",
    "            t = i - 1\n",
    "            ans = (ans * (2 * t + 1) * (t + 1)) % mod \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        mod = int(10**9 + 7)\n",
    "        ans = 1\n",
    "        for i in range(2, n + 1):\n",
    "            ans = (ans % mod) * (i * (i * 2 - 1) % mod ) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 1000000007\r\n",
    "from functools import reduce\r\n",
    "class Solution:\r\n",
    "    def countOrders(self, n: int) -> int:\r\n",
    "        #   nCr(2n, 2) * nCr(2n - 2, 2) * .. * nCr(2, 2)\r\n",
    "        # = 2n * (2n - 1) * (2n - 2) * .. * 2 / 2^n\r\n",
    "        return (reduce(lambda x, y: (x * y) % mod, range(2, 2 * n + 1), 1) * pow(pow(2, n, mod), mod - 2, mod)) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        dp = 1\n",
    "        for i in range(2, n+1):\n",
    "            dp = dp * i * (2 * i - 1) % (10 ** 9 + 7)\n",
    "        return dp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        # dp = [0, 1]\n",
    "        mod = 10 ** 9 + 7\n",
    "        # def seqSum(n: int) -> int:\n",
    "        #     return sum([x for x in range(n+1)])\n",
    "        choices = 1\n",
    "        dp = 1\n",
    "        for i in range(2, n+1):\n",
    "            choices += 4 * i - 3\n",
    "            # dp.append(dp[i-1] * choices % mod)\n",
    "            dp = dp * choices % mod\n",
    "            # print(dp)\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        mod=10**9+7\n",
    "        \n",
    "        f=[0]*(n*2+10)\n",
    "        f[0]=1\n",
    "        for i in range(1,n+1):\n",
    "            x=(n-i+1)\n",
    "            f[i]=x*(2*x-1)*f[i-1]%mod\n",
    "        return  f[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        ans, mod = 1, int(10**9 + 7)\n",
    "        for i in range(2, n + 1):\n",
    "            ans = (ans % mod) * (i * (i * 2 - 1) % mod ) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        modulo = 10**9+7\n",
    "        n *= 2\n",
    "        rst = 1\n",
    "        while n>0:\n",
    "            rst *= comb(n, 2)\n",
    "            rst %= modulo\n",
    "            n -= 2\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        ans = 1\n",
    "        for i in range(n):\n",
    "            ans = (ans * (2 * i + 1) * (i + 1)) % mod \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        ans = 1\n",
    "        for i in range(2, n + 1):\n",
    "            ans = ans * (i * 2 - 1) % mod * i % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10**9 + 7\n",
    "@lru_cache(None)\n",
    "def dfs(n):\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    res = dfs(n-1)*(2*n-1+1)*(2*n-1)//2\n",
    "    \n",
    "    return res % mod\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        ans, mod = 1, int(1e9 + 7)\n",
    "        for i in range(2, n + 1):\n",
    "            ans = ans * (i * 2 - 1) * i % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        # factor1=math.factorial(n)%(1e9+7)\n",
    "        factor2=1\n",
    "        for i in range(1, n+1):\n",
    "            factor2*=2*i-1\n",
    "            factor2 = (i*factor2) % (1e9+7)\n",
    "\n",
    "        # return int((factor1*factor2)%(1e9+7))\n",
    "        return int((factor2)%(1e9+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 1\n",
    "        ans,mod=1,int(1e9+7)\n",
    "        for i in range(2,n+1):\n",
    "            ans=ans*(i*2-1)*i%mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        \n",
    "        # 初始化第一笔订单的可能情况数\n",
    "        dp = [1] * (n + 1)\n",
    "        \n",
    "        for i in range(2, n + 1):\n",
    "            # 计算第 i 笔订单的可能情况数\n",
    "            # 新的订单可以在之前的订单之间的任意位置插入（包括首尾），有 i - 1 个位置可选\n",
    "            # 同时，新的订单可以选择是配送还是收件，有 2 种选择\n",
    "            dp[i] = dp[i - 1] * (i * 2 - 1) * i % MOD\n",
    "        \n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        mod=10**9+7\n",
    "        # x=factorial(2*n)%mod\n",
    "        # y=pow(2,n,mod)\n",
    "        # return (x*pow(y,mod-2,mod))%(mod)\n",
    "        f=[1]*(n+1)\n",
    "        for i in range(2,n+1):\n",
    "            f[i]=f[i-1]*(2*(i-1)+1)+f[i-1]*comb(2*(i-1)+1,2)\n",
    "            f[i]%=mod\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        ans = 1\n",
    "        for i in range (1,n):\n",
    "            ans *= (i + 1) * (2 * i + 1)\n",
    "        return ans % (10 ** 9 + 7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        ans = 1\n",
    "        mod = int(10 ** 9 + 7)\n",
    "        for i in range(1, n):\n",
    "            a = 2 * i + 1\n",
    "            b = a * (a - 1) // 2\n",
    "            ans = (ans * (a + b)) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        count = 1\n",
    "        for i in range(2, n + 1):\n",
    "            count = (count * i * (2 * i - 1)) % MOD\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        slots = 2 * n\n",
    "        output = 1\n",
    "        while slots > 0:\n",
    "            valid_choices = slots * (slots - 1) // 2\n",
    "            output *= valid_choices\n",
    "            slots -= 2\n",
    "        return output % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        dp = 1\n",
    "        for i in range(2, n+1):\n",
    "            dp = dp * i * (2 * i - 1) % (10 ** 9 + 7)\n",
    "        return dp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        ans, mod = 1, int(1e9 + 7)\n",
    "        for i in range(2, n + 1):\n",
    "            ans = ans * (i * 2 - 1) * i % mod\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        pre = 1\n",
    "        size = 2\n",
    "        for i in range(2, n + 1):\n",
    "            pre = pre * (size + 1) * (size + 2) // 2\n",
    "            size += 2\n",
    "            pre %= int(1e9 + 7)\n",
    "        return pre            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        ans = 1\n",
    "        cur = 1\n",
    "        for i in range (1,n):\n",
    "            ans *= (i+1) * (2 * i + 1)\n",
    "        return ans % (10**9 + 7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        res = 1\n",
    "        for i in range(2, n + 1):\n",
    "            current = 2 * (i - 1)\n",
    "            res *= ((1 + current + 1) * (current + 1) // 2) \n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = 0\n",
    "        dp[1] = 1\n",
    "        for i in range(2, n+1):\n",
    "            dp[i] = dp[i-1] * i * (2 * i - 1)\n",
    "        return dp[n] % (10 ** 9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        ans, mod = 1, int(1e9 + 7)\n",
    "        for i in range(2, n + 1):\n",
    "            ans = ans * (i * 2 - 1) * i % mod\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        \n",
    "        x=factorial(2*n)\n",
    "        y=pow(2,n)\n",
    "        return (x//y)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        # dp = [0, 1]\n",
    "        mod = 10 ** 9 + 7\n",
    "        # def seqSum(n: int) -> int:\n",
    "        #     return sum([x for x in range(n+1)])\n",
    "        choices = 1\n",
    "        dp = 1\n",
    "        for i in range(2, n+1):\n",
    "            choices += 4 * i - 3\n",
    "            # dp.append(dp[i-1] * choices % mod)\n",
    "            dp = dp * choices % mod\n",
    "            # print(dp)\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dp = [1]\n",
    "for i in range(1, 501):\n",
    "    dp.append(dp[-1] * (2 * i - 1) * i % (10 ** 9 + 7))\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        # 从低到高，从特殊到一般\n",
    "        # n == 1, p1 d1\n",
    "        # n == 2, p1 d1, 若p2d2连续则有C(3, 1), 否则有C(3, 2)\n",
    "        # n == 3, p1 d1 p2 d2若p3d3连续则有C(5, 1), 否则有C(5, 2)\n",
    "        # n == n, C(2n - 1, 1) + C(2n - 1, 2)\n",
    "        return reduce(mul, [comb(2*x-1, 1) + comb(2*x-1, 2) for x in range(1, n + 1)]) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        MAX = 10**9 + 7\n",
    "        # dp[i]: n=i时的排列方式, dp[i] = dp[i-1] * (insert_num)\n",
    "        dp = [0] * n\n",
    "        dp[0] = 1\n",
    "        for i in range(1, n):\n",
    "            # 把(P2, D2).. 放进去\n",
    "            space = 2 * i + 1\n",
    "            res = 0\n",
    "            # 情况一：间隔插入, P2, P1, D2\n",
    "            res += (space) * (space-1) // 2 + space\n",
    "            # 情况二：直接两个一起插入, P2, D2, P1\n",
    "            # res += space\n",
    "            dp[i] = (dp[i-1] * res) % MAX\n",
    "        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        # ans = (2n)! / 2^n\n",
    "        mod = 1000000007\n",
    "        res = 1\n",
    "        for i in range(1, 2 * n + 1):\n",
    "            if i % 2 != 0:\n",
    "                res = res * i\n",
    "            else:\n",
    "                res = res * i // 2\n",
    "        return res % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        mod=10**9+7\n",
    "        x=factorial(2*n)%mod\n",
    "        y=pow(2,n,mod)\n",
    "        return (x*pow(y,mod-2,mod))%(mod)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countOrders(self, n: int) -> int:\r\n",
    "        MOD = 1000000007\r\n",
    "        ans = 1 # base case: n=1\r\n",
    "        for i in range(2, n+1):\r\n",
    "            cur = math.comb(2*i-1, 2) + math.comb(2*i-1, 1)\r\n",
    "            ans = ans * cur % MOD\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[1] = 1\n",
    "        mod = 10**9 + 7\n",
    "        for i in range(2, n + 1):\n",
    "            t = 2 * i - 1 + math.comb(2 * i - 1, 2)\n",
    "            dp[i] = dp[i - 1] * t % mod\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        res = [1,6,90,2520,113400,7484400,681080400,729647433,636056472,850728840,518360668,67543367,951594128,702577871,621371750,200385844,416457700,368349166,949461892,580270580,612965887,865725049,25419443,673131508,586091532,157365993,190734408,730986269,320294201,920731808,103836741,334868393,292697959,765945940,759432157,108579705,273781154,276283440,679164517,159858698,890732348,92943393,708099042,603113806,470776125,668845460,523485199,92490731,608441370,784760423,300910579,677049847,782372186,546459068,22089728,309748289,88715484,732274143,888373751,988537746,397052154,919705215,678517431,989640570,136121364,905304912,172014363,91841287,175679935,365755587,579155830,988383946,43995176,579521182,149163518,800520591,933016561,170143530,290187820,189044563,330128828,501884164,303577869,590316526,896836637,879491406,225059047,909299545,195632117,633382813,448239899,566886742,286327839,70718711,754447122,542332161,315010,19841058,960151472,14159051,442892342,528769262,962888982,73859393,844368045,135562275,599787902,74986951,666339592,120658916,883847683,979576090,721913915,688161603,735688151,499556205,401609179,622455718,118491869,346779134,426255790,779061888,29830541,649803357,129345050,666522670,39759858,761756041,497850495,626049316,252013521,901333800,509558631,988572308,3113720,759263522,214787543,187199793,753579430,812329762,317274907,9323452,977283607,176627373,570013758,604352869,82238489,532404610,501041410,707081203,547532594,160972745,793092848,843405279,895554947,743504516,555165004,562055670,291736707,241421050,881197718,551469305,86227877,228555388,129150731,316015854,957533783,930010,966859166,93346540,130055839,774223940,555535437,118380392,82390790,773407417,268483316,460619285,953963317,109113025,554116622,268492796,976183289,704678159,854187407,55794834,745439097,455970629,275000714,801276526,693665383,377247225,354857408,984291337,418845494,643053498,844520163,921485887,149021061,880584563,995865538,429418945,678316047,224356083,135647458,727598640,134896819,293334572,987774568,283629922,129424817,299808050,123536270,497201044,337972327,871534151,219788881,579439336,82385030,746141708,716494355,353343582,50114322,846798097,777150596,851093419,786756563,125274294,330598212,252996533,853607116,61330419,844200047,492090302,732255285,567889702,3038275,476986349,874364408,931640068,647566656,475623379,592939667,834257077,168410349,612271927,964300825,568448361,189526404,418733499,155864157,716946400,656154800,302242914,618748027,141333438,541668927,549826693,443157418,661566327,450082067,944881038,448408602,191542354,364707533,479845527,296314888,628344045,181697023,367572096,112189426,929346513,819968801,283096013,420263495,990818243,528218565,841823364,875319945,76832365,930766188,23569590,659566674,701637416,30769173,790530770,574747249,143768154,770816151,739008421,891872283,768905992,330636202,534069336,216827101,865475026,325987150,781161900,741659627,234038968,883053809,395816091,26213752,171195197,651644179,304718069,197721764,456274716,142820618,848196185,976258551,230780849,503269603,712205860,907083316,783611060,177809980,169010065,351997794,508413288,625819891,504244975,876131268,644162677,11695135,11703136,982315730,709955920,100901547,59272489,287050023,302420380,480580317,721111192,833663803,505053490,635783668,42838822,638096649,991356970,905318879,814189811,965704426,993990174,432656738,168137374,162180130,885967232,185577098,436707893,413028379,349838382,528326996,622979292,771802340,519723955,54303618,97002160,646815704,775651413,324013844,846741130,95327863,421553382,30864287,616471903,721937074,538408637,843033114,542747450,243182501,670075898,39612302,805630694,519593283,671853368,404626126,249290808,280186970,525321723,304622159,1573585,52533848,689075440,118715523,451690628,702110967,766299032,179697784,983374889,171126761,963146628,548391195,43772902,43677316,307658809,453230190,563414058,359432005,467993882,101840042,576367734,337116736,494435245,234714032,349919531,222721626,394559107,108358470,690386605,840881056,582948402,92881075,436473750,245530116,778386590,142396323,588268790,628015221,2026880,639154661,712440474,159041633,303176212,555929149,769259608,194320132,508606317,636955071,92928366,880025918,740348479,819126004,92375579,354251252,37512809,174046132,179622079,38797152,186402485,279367738,316229837,487877182,693487723,208736986,155337953,405602921,546065750,617470247,586675271,81377349,653025946,780077871,903316112,24727391,153787752,554983070,753516868,508071705,231068226,177776557,545564626,688564593,909184714,155928012,743820616,822149346,108304388,687886606,993700892,162961279,412930053,538448194,546734453,221325897,921049056,397994699,598874750,980102575,814165880,847902700,601893231,423539172,190205220,795591577,436107654,46509004,983948304,250790324,625483898,452524619,195102685,838686231,952276050,498394413,794473522,364306339,432774271,496638171,764678010]\n",
    "        return res[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "\r\n",
    "    def countOrders(self, n: int) -> int:\r\n",
    "        MOD = 10**9 + 7\r\n",
    "        if n == 1:\r\n",
    "            return 1\r\n",
    "        ans = 1\r\n",
    "        for i in range(2, n + 1):\r\n",
    "            ans = ans * (2 * i - 1) * i % MOD\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        # f[i] = f[i-1]*i*(2*i-1)\n",
    "        f = [1]*(n+1)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        for i in range(2,n+1):\n",
    "            f[i] = f[i-1]*i*(2*i-1)\n",
    "        return f[n]%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        \n",
    "        MOD = int(1e9) + 7\n",
    "        ans = self.countOrders(n-1) * comb(2*n, 2)\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "      def g(i):\n",
    "          if i==1:\n",
    "            return 1\n",
    "          return g(i-1)*i*(2*i-1)%(10**9+7)\n",
    "      return g(n)%(10**9+7)   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        time = (n*2*(n*2-1))//2\n",
    "        return (self.countOrders(n-1) * time)%(10**9+7) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "res = [1,6,90,2520,113400,7484400,681080400,729647433,636056472,850728840,518360668,67543367,951594128,702577871,621371750,200385844,416457700,368349166,949461892,580270580,612965887,865725049,25419443,673131508,586091532,157365993,190734408,730986269,320294201,920731808,103836741,334868393,292697959,765945940,759432157,108579705,273781154,276283440,679164517,159858698,890732348,92943393,708099042,603113806,470776125,668845460,523485199,92490731,608441370,784760423,300910579,677049847,782372186,546459068,22089728,309748289,88715484,732274143,888373751,988537746,397052154,919705215,678517431,989640570,136121364,905304912,172014363,91841287,175679935,365755587,579155830,988383946,43995176,579521182,149163518,800520591,933016561,170143530,290187820,189044563,330128828,501884164,303577869,590316526,896836637,879491406,225059047,909299545,195632117,633382813,448239899,566886742,286327839,70718711,754447122,542332161,315010,19841058,960151472,14159051,442892342,528769262,962888982,73859393,844368045,135562275,599787902,74986951,666339592,120658916,883847683,979576090,721913915,688161603,735688151,499556205,401609179,622455718,118491869,346779134,426255790,779061888,29830541,649803357,129345050,666522670,39759858,761756041,497850495,626049316,252013521,901333800,509558631,988572308,3113720,759263522,214787543,187199793,753579430,812329762,317274907,9323452,977283607,176627373,570013758,604352869,82238489,532404610,501041410,707081203,547532594,160972745,793092848,843405279,895554947,743504516,555165004,562055670,291736707,241421050,881197718,551469305,86227877,228555388,129150731,316015854,957533783,930010,966859166,93346540,130055839,774223940,555535437,118380392,82390790,773407417,268483316,460619285,953963317,109113025,554116622,268492796,976183289,704678159,854187407,55794834,745439097,455970629,275000714,801276526,693665383,377247225,354857408,984291337,418845494,643053498,844520163,921485887,149021061,880584563,995865538,429418945,678316047,224356083,135647458,727598640,134896819,293334572,987774568,283629922,129424817,299808050,123536270,497201044,337972327,871534151,219788881,579439336,82385030,746141708,716494355,353343582,50114322,846798097,777150596,851093419,786756563,125274294,330598212,252996533,853607116,61330419,844200047,492090302,732255285,567889702,3038275,476986349,874364408,931640068,647566656,475623379,592939667,834257077,168410349,612271927,964300825,568448361,189526404,418733499,155864157,716946400,656154800,302242914,618748027,141333438,541668927,549826693,443157418,661566327,450082067,944881038,448408602,191542354,364707533,479845527,296314888,628344045,181697023,367572096,112189426,929346513,819968801,283096013,420263495,990818243,528218565,841823364,875319945,76832365,930766188,23569590,659566674,701637416,30769173,790530770,574747249,143768154,770816151,739008421,891872283,768905992,330636202,534069336,216827101,865475026,325987150,781161900,741659627,234038968,883053809,395816091,26213752,171195197,651644179,304718069,197721764,456274716,142820618,848196185,976258551,230780849,503269603,712205860,907083316,783611060,177809980,169010065,351997794,508413288,625819891,504244975,876131268,644162677,11695135,11703136,982315730,709955920,100901547,59272489,287050023,302420380,480580317,721111192,833663803,505053490,635783668,42838822,638096649,991356970,905318879,814189811,965704426,993990174,432656738,168137374,162180130,885967232,185577098,436707893,413028379,349838382,528326996,622979292,771802340,519723955,54303618,97002160,646815704,775651413,324013844,846741130,95327863,421553382,30864287,616471903,721937074,538408637,843033114,542747450,243182501,670075898,39612302,805630694,519593283,671853368,404626126,249290808,280186970,525321723,304622159,1573585,52533848,689075440,118715523,451690628,702110967,766299032,179697784,983374889,171126761,963146628,548391195,43772902,43677316,307658809,453230190,563414058,359432005,467993882,101840042,576367734,337116736,494435245,234714032,349919531,222721626,394559107,108358470,690386605,840881056,582948402,92881075,436473750,245530116,778386590,142396323,588268790,628015221,2026880,639154661,712440474,159041633,303176212,555929149,769259608,194320132,508606317,636955071,92928366,880025918,740348479,819126004,92375579,354251252,37512809,174046132,179622079,38797152,186402485,279367738,316229837,487877182,693487723,208736986,155337953,405602921,546065750,617470247,586675271,81377349,653025946,780077871,903316112,24727391,153787752,554983070,753516868,508071705,231068226,177776557,545564626,688564593,909184714,155928012,743820616,822149346,108304388,687886606,993700892,162961279,412930053,538448194,546734453,221325897,921049056,397994699,598874750,980102575,814165880,847902700,601893231,423539172,190205220,795591577,436107654,46509004,983948304,250790324,625483898,452524619,195102685,838686231,952276050,498394413,794473522,364306339,432774271,496638171,764678010]\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "\n",
    "        return res[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        return self.countOrders(n-1) * n * (2*n-1) %(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "      def g(i):\n",
    "         if i==1:\n",
    "           return 1\n",
    "         return g(i-1)*i*(2*i-1)%(10**9+7)\n",
    "      return g(n)%(10**9+7)   \n",
    "         \n",
    "           \n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "\n",
    "        # 2*n\n",
    "        # (2*n)! / 2^n\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def dfs(n):\n",
    "            if n == 2:\n",
    "                return 1\n",
    "            return (dfs(n-2) * n * (n-1) >> 1) % MOD\n",
    "        return dfs(2*n)\n",
    "\n",
    "\n",
    "        # MOD = 10 ** 9 + 7\n",
    "        # def factorial(n):\n",
    "        #     if n == 1:\n",
    "        #         return 1\n",
    "        #     return factorial(n-1) * n \n",
    "        # return factorial(2*n) % MOD >> n\n",
    "\n",
    "        # MOD = 10 ** 9 + 7\n",
    "        # def factorial(n):\n",
    "        #     if n == 1:\n",
    "        #         return 1\n",
    "        #     return (factorial(n-1) * n) % MOD\n",
    "        # return factorial(2*n) >> n\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        \n",
    "        MOD = int(1e9) + 7\n",
    "        ans = self.countOrders(n-1) * (2*n-1) * (n)\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        def coco(num):\n",
    "            if num == 1:\n",
    "                return 1\n",
    "            return (num * 2 -1) * num * coco(num-1)\n",
    "        return coco(n) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countOrders(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        t = n * 2 - 1\n",
    "        return t * (1 + t) // 2 * self.countOrders(n-1) % (10 ** 9 + 7)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
